home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / incl / LEDA.020+881 / graph2.h < prev    next >
C/C++ Source or Header  |  1994-08-05  |  28KB  |  969 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  graph2.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_GRAPH1_H
  17. #define LEDA_GRAPH1_H
  18.  
  19. //------------------------------------------------------------------------------
  20. //   directed graphs
  21. //------------------------------------------------------------------------------
  22.  
  23.  
  24. #include <LEDA/basic.h>
  25. #include <LEDA/list.h>
  26. #include <LEDA/impl/olist.h>
  27.  
  28.  
  29. class node_struct;
  30. typedef node_struct* node;
  31.  
  32. class edge_struct;
  33. typedef edge_struct* edge;
  34.  
  35.  
  36. class node_link_struct : public obj_link {};
  37. typedef node_link_struct* node_link;
  38.  
  39. class edge_link_struct : public obj_link {};
  40. typedef edge_link_struct* edge_link;
  41.  
  42. class aux_link_struct : public obj_link {};
  43. typedef aux_link_struct* aux_link;
  44.  
  45.  
  46. typedef int  (*cmp_graph_node) (node&, node&);
  47. typedef int  (*cmp_graph_edge) (edge&, edge&);
  48.  
  49.  
  50. //------------------------------------------------------------------------------
  51. // class node_struct: internal representation of nodes
  52. //------------------------------------------------------------------------------
  53.  
  54. class node_struct : public aux_link_struct, 
  55.                     public node_link_struct
  56. {  
  57.    friend class graph;
  58.    friend class ugraph;
  59.    friend class planar_map;
  60.    friend class node_data;
  61.    friend class node_stack;
  62.    friend class node_queue;
  63.    friend class node_list;
  64.    friend class node_pq;
  65.    friend class node_bucket_pq;
  66.  
  67.    
  68.    graph*   g;            // pointer to graph of node 
  69.    int      name;         // internal name (index)  
  70.    obj_list adj_edges;    // lists of adjacent edges
  71.    int      indegree;
  72.  
  73. public:
  74.  
  75.    GenPtr data[3];      // data[0] used by GRAPH
  76.                         // data[1] in node_stack, node_queue, node_pq, etc.
  77.                         // data[2] used by node_data
  78.  
  79.  
  80. node_struct(GenPtr i=0) { data[0] = i; name = -1; g = 0; indegree=0; }
  81.  
  82. LEDA_MEMORY(node_struct)
  83.  
  84. FRIEND_INLINE graph* graph_of(node);
  85. FRIEND_INLINE graph* graph_of(edge);
  86. FRIEND_INLINE int    indeg(node);
  87. FRIEND_INLINE int    outdeg(node);
  88. FRIEND_INLINE int    degree(node);
  89. FRIEND_INLINE int    index(node);
  90.  
  91. FRIEND_INLINE edge First_Adj_Edge(node);
  92. FRIEND_INLINE edge Last_Adj_Edge(node);
  93.  
  94. FRIEND_INLINE void start_adj_iteration(node);
  95. FRIEND_INLINE void move_to_adj_succ(node);
  96. FRIEND_INLINE bool read_adj_node(node&,node);
  97. FRIEND_INLINE bool read_adj_edge(edge&,node);
  98.  
  99. friend void init_node_data1(const graph&,GenPtr);
  100. friend void init_node_data2(const graph&,GenPtr);
  101.  
  102. };
  103.  
  104.  
  105.  
  106. //------------------------------------------------------------------------------
  107. // class edge_struct: internal representation of edges
  108. //------------------------------------------------------------------------------
  109.  
  110. class adj_link_struct1 : public obj_link 
  111. {
  112.    friend class graph;
  113.    friend class ugraph;
  114.    friend class planar_map;
  115.  
  116.  protected:
  117.  
  118.    int  name;          // internal name (index)  
  119.    node s;             // source node 
  120.    node t;             // target node
  121.  
  122.    LEDA_MEMORY(adj_link_struct1)
  123.  
  124.    adj_link_struct1() { name = -1; }
  125.  
  126.  };
  127.  
  128. typedef adj_link_struct1* adj_link1;
  129.  
  130.  
  131. class edge_struct : public adj_link_struct1, 
  132.                     public edge_link_struct
  133. { 
  134.    
  135.    friend class graph;
  136.    friend class ugraph;
  137.    friend class planar_map;
  138.    friend class edge_data;
  139.  
  140.    edge rev;     // reverse edge (for ugraph/planar_map)
  141.  
  142. public:
  143.  
  144.    GenPtr data[1];     // space for data data[0] used by GRAPH!)
  145.                        //                data[1] by edge_data
  146.  
  147.  
  148. edge_struct(node v, node w, GenPtr i=0)
  149. { data[0] = i;
  150.   name = -1;
  151.   s = v;
  152.   t = w;
  153.   rev = nil;
  154. }
  155.  
  156. LEDA_MEMORY(edge_struct)
  157.  
  158. FRIEND_INLINE graph* graph_of(edge);
  159. FRIEND_INLINE node   source(edge);
  160. FRIEND_INLINE node   target(edge);
  161. FRIEND_INLINE int    index(edge);
  162.  
  163. FRIEND_INLINE bool read_adj_node(node&,node);
  164.  
  165. FRIEND_INLINE void init_edge_data(const graph&,int,GenPtr);
  166.  
  167. };
  168.  
  169.  
  170. inline int    outdeg(node v) { return v->adj_edges.length(); }
  171. inline int    indeg(node v)  { return v->indegree; }
  172. inline int    degree(node v) { return outdeg(v); }
  173.  
  174. inline int     index(node v)  { return v->name;    }
  175. inline graph*  graph_of(node v) { return v->g; }
  176.  
  177. inline graph* graph_of(edge e) { return e->s->g;   }
  178. inline node   source(edge e)   { return e->s;      }
  179. inline node   target(edge e)   { return e->t;      }
  180. inline int    index(edge e)    { return e->name;    }
  181.  
  182.  
  183. inline edge First_Adj_Edge(node v)  
  184. { return edge(adj_link1(v->adj_edges.first())); }
  185.  
  186. inline edge Last_Adj_Edge(node v)  
  187. { return edge(adj_link1(v->adj_edges.last())); }
  188.  
  189. inline edge Succ_Adj_Edge(edge e) 
  190. { return edge(adj_link1(adj_link1(e)->succ_item()));}
  191.  
  192. inline edge Pred_Adj_Edge(edge e) 
  193. { return edge(adj_link1(adj_link1(e)->pred_item()));}
  194.  
  195. inline void start_adj_iteration(node v) { v->adj_edges.start_iteration(); }
  196.  
  197. inline void move_to_adj_succ(node v) { v->adj_edges.move_to_succ(); }
  198.  
  199. inline bool read_adj_edge(edge& e, node v)
  200. { obj_link* p = v->adj_edges.read_iterator();
  201.   if (p) { e = edge(adj_link1(p)); return true; }
  202.   else return false;
  203.  }
  204.  
  205. inline bool read_adj_node(node& u, node v)
  206. { obj_link* p = v->adj_edges.read_iterator();
  207.   if (p) { u = edge(adj_link1(p))->t; return true; }
  208.   else return false;
  209.  }
  210.  
  211.  
  212.  
  213. //------------------------------------------------------------------------------
  214. // graph_array<node/edge>
  215. //
  216. // base class for node and edge arrays
  217. //
  218. //------------------------------------------------------------------------------
  219.  
  220. template <class itype>
  221.  
  222. class _CLASSTYPE graph_array {
  223.  
  224. graph* g;     // array is declared for graph *g 
  225.  
  226. int mx_i;    // maximal node index in g at time of creation
  227.  
  228. protected:
  229.  
  230. GenPtr* arr;  
  231.  
  232. virtual void clear_entry(GenPtr&) const {}
  233. virtual void copy_entry(GenPtr&)  const {}
  234.  
  235. public:
  236.  
  237. virtual int cmp_entry(itype,itype) const  { return 0; }
  238.  
  239.  GenPtr& entry(itype x)
  240.  { if (g != graph_of(x) || index(x) > mx_i)
  241.           error_handler(102,"(node/edge)_array[x]: not defined for x");
  242.   return arr[index(x)];
  243.  }
  244.  
  245.  GenPtr  inf(itype x) const
  246.  { if (g != graph_of(x) || index(x) > mx_i)
  247.           error_handler(102,"(node/edge)_array[x]: not defined for x");
  248.   return arr[index(x)];
  249.  }
  250.  
  251.  GenPtr& entry(int i) { return arr[i]; }
  252.  
  253.  void init(const graph&, int, GenPtr);
  254.  void init(const graph_array<itype>&);
  255.  
  256.  void clear();
  257.  int  size() const     { return mx_i+1;}
  258.  
  259.  graph_array() { g = 0; mx_i = -1; arr = 0;}
  260.  
  261.  virtual ~graph_array() { clear(); }
  262.  
  263. };
  264.  
  265.  
  266. //------------------------------------------------------------------------------
  267. // graph: base class for all graphs
  268. //------------------------------------------------------------------------------
  269.  
  270. class graph {
  271.  
  272. friend class ugraph;
  273. friend class planar_map;
  274. friend class graph_array<node>; 
  275. friend class graph_array<edge>; 
  276.  
  277. //list<node> V;              /* list of all nodes */
  278. obj_list V;
  279.  
  280. //list<edge> E;              /* list of all edges */
  281. obj_list E;
  282.  
  283. int max_n_index;      // maximal node index 
  284. int max_e_index;      // maximal edge index
  285.  
  286. bool   undirected;       // true iff graph undirected
  287.  
  288.  
  289. /* space: 2 lists + 4 words + "virtual" = 2*20 + 5*4 bytes = 60 bytes */
  290.  
  291. virtual void init_node_entry(GenPtr& x)  { x=0; }
  292. virtual void init_edge_entry(GenPtr& x)  { x=0; }
  293.  
  294. virtual void copy_node_entry(GenPtr&) const {}
  295. virtual void copy_edge_entry(GenPtr&) const {}
  296.  
  297. virtual void clear_node_entry(GenPtr& x) const { x=0; }
  298. virtual void clear_edge_entry(GenPtr& x) const { x=0; }
  299.  
  300. virtual void read_node_entry(istream& in, GenPtr& x)  { Read(x,in); }
  301. virtual void read_edge_entry(istream& in, GenPtr& x)  { Read(x,in); }
  302.  
  303. virtual void write_node_entry(ostream& o, GenPtr& x)  const { Print(x,o); }
  304. virtual void write_edge_entry(ostream& o, GenPtr& x)  const { Print(x,o); }
  305.  
  306. virtual void print_node_entry(ostream&, GenPtr&)  const {}
  307. virtual void print_edge_entry(ostream&, GenPtr&)  const {}
  308.  
  309. virtual char* node_type()  const { return "void"; }
  310. virtual char* edge_type()  const { return "void"; }
  311.  
  312. protected:
  313.  
  314. graph* parent;           // for subgraphs
  315.  
  316. void copy_all_entries() const;
  317. void clear_all_entries() const;
  318.  
  319. public:
  320.  
  321. virtual int cmp_node_entry(node, node) const { return 0; }
  322. virtual int cmp_edge_entry(edge, edge) const { return 0; }
  323.  
  324.    int  space() const;
  325.    void reset() const;
  326.  
  327.  
  328.    int  indeg(node v)     const;
  329.    int  outdeg(node v)    const;
  330.    int  degree(node v)    const;
  331.    node source(edge e)    const;
  332.    node target(edge e)    const;
  333.  
  334.    graph* super()        const;
  335.  
  336.    int max_i(node)       const;
  337.    int max_i(edge)       const;
  338.    int max_node_index()  const;
  339.    int max_edge_index()  const;
  340.  
  341.    int  number_of_nodes() const;
  342.    int  number_of_edges() const;
  343.  
  344.    list<edge> all_edges()     const;
  345.    list<node> all_nodes()     const;
  346.    list<edge> adj_edges(node) const;
  347.    list<node> adj_nodes(node) const;
  348.  
  349.    GenPtr& entry(node v);
  350.    GenPtr& entry(edge e);
  351.    GenPtr  inf(node v) const;
  352.    GenPtr  inf(edge e) const;
  353.  
  354. int int_inf(edge e) { return int(e->data[0]); }
  355.  
  356.  
  357.    edge first_adj_edge(node v) const;
  358.    //edge first_in_edge(node v)  const;
  359.    edge last_adj_edge(node v)  const;
  360.    //edge last_in_edge(node v)   const;
  361.  
  362.    void init_adj_iterator(node v)        const;
  363.    edge next_adj_edge(edge& e,node v)    const;
  364.    bool current_adj_edge(edge& e,node v) const;
  365.    bool next_adj_node(node& w,node v)    const;
  366.    bool current_adj_node(node& w,node v) const;
  367.  
  368.    void init_node_iterator() const {}
  369.    void init_edge_iterator() const {}
  370.    
  371.    node first_node()      const;
  372.    edge first_edge()      const;
  373.    node last_node()       const;
  374.    edge last_edge()       const;
  375.    node choose_node()     const;
  376.    edge choose_edge()     const;
  377.    node succ_node(node v) const;
  378.    node pred_node(node v) const;
  379.    edge succ_edge(edge e) const;
  380.    edge pred_edge(edge e) const;
  381.    edge adj_succ(edge e)  const;
  382.    edge adj_pred(edge e)  const;
  383.    edge cyclic_adj_succ(edge e) const;
  384.    edge cyclic_adj_pred(edge e) const;
  385.  
  386. protected:
  387.  
  388.    node new_node(GenPtr);
  389.    edge new_edge(node, node, GenPtr);
  390.    edge new_edge(edge, node, GenPtr, int dir);
  391.  
  392.    void assign(node v,GenPtr x);
  393.    void assign(edge e,GenPtr x);
  394.  
  395. public:
  396.  
  397.    node new_node()   { GenPtr x; init_node_entry(x);  
  398.                        return new_node(x); }
  399.  
  400.    edge new_edge(node v, node w) 
  401.    { GenPtr x; init_edge_entry(x);
  402.      return new_edge(v,w,x);}
  403.  
  404.    edge new_edge(edge e, node w, int dir=0) 
  405.    { GenPtr x; init_edge_entry(x);
  406.      return new_edge(e,w,x,dir); }
  407.  
  408.    void del_node(node);
  409.    void del_edge(edge);
  410.    void del_all_nodes(); 
  411.    void del_all_edges(); 
  412.  
  413.    list<edge> insert_reverse_edges();
  414.  
  415.    void sort_nodes(cmp_graph_node);
  416.    void sort_edges(cmp_graph_edge);
  417.  
  418.    void sort_nodes(const graph_array<node>&);
  419.    void sort_edges(const graph_array<edge>&);
  420.  
  421.    void sort_edges();
  422.    void sort_nodes();
  423.  
  424.    edge rev_edge(edge);
  425.    graph& rev();
  426.  
  427.    void make_directed();
  428.    void make_undirected();
  429.  
  430.    void write(ostream& = cout) const;
  431.    void write(string) const;
  432.  
  433.    int  read(istream& = cin);
  434.    int  read(string);
  435.  
  436.    void print_node(node,ostream& = cout)  const;
  437.  
  438. virtual void print_edge(edge,ostream& = cout)  const;  //different for ugraph's
  439.  
  440.    void print(string s, ostream& = cout) const;
  441.  
  442.    void print()           const { print("");   }
  443.    void print(ostream& o) const { print("",o); }
  444.  
  445.    void clear();
  446.  
  447.    graph();
  448.    graph(const graph&);
  449.    graph& operator=(const graph&); 
  450.  
  451.   virtual ~graph(){ clear(); }
  452.  
  453.  
  454.    //subgraph constructors
  455.  
  456.    graph(graph&, const list<node>&, const list<edge>&);
  457.    graph(graph&, const list<edge>&);
  458.  
  459. };
  460.  
  461. inline int  graph::outdeg(node v) const { return v->adj_edges.length(); }
  462. inline int  graph::indeg(node v)  const { return v->indegree; }
  463. inline int  graph::degree(node v) const { return outdeg(v); }
  464.  
  465. inline node graph::source(edge e)    const   { return e->s; }
  466. inline node graph::target(edge e)    const   { return e->t; }
  467.  
  468. inline graph* graph::super()       const   { return parent; }
  469. inline int graph::max_i(node)      const   { return max_n_index; }
  470. inline int graph::max_i(edge)      const   { return max_e_index; }
  471. inline int graph::max_node_index() const   { return max_n_index; }
  472. inline int graph::max_edge_index() const   { return max_e_index; }
  473.  
  474. inline int  graph::number_of_nodes() const   { return V.length(); }
  475. inline int  graph::number_of_edges() const   { return E.length(); }
  476.  
  477. inline GenPtr& graph::entry(node v)        { return v->data[0]; }
  478. inline GenPtr& graph::entry(edge e)        { return e->data[0]; }
  479. inline void graph::assign(node v,GenPtr x) { v->data[0] = x; }
  480. inline void graph::assign(edge e,GenPtr x) { e->data[0] = x; }
  481.  
  482. inline GenPtr  graph::inf(node v) const { return v->data[0]; }
  483. inline GenPtr  graph::inf(edge e) const { return e->data[0]; }
  484.  
  485. inline edge graph::first_adj_edge(node v) const
  486. { return edge(adj_link1(v->adj_edges.first())); }
  487.  
  488. inline edge graph::last_adj_edge(node v)  const
  489. { return edge(adj_link1(v->adj_edges.last())); }
  490.  
  491.  
  492. inline void graph::init_adj_iterator(node v) const 
  493. { v->adj_edges.set_iterator(nil); }
  494.  
  495. inline bool  graph::current_adj_edge(edge& e,node v) const 
  496. { return (e = edge(adj_link1(v->adj_edges.read_iterator()))) != nil;}
  497.  
  498. inline edge  graph::next_adj_edge(edge& e,node v) const 
  499. { obj_link* it = v->adj_edges.read_iterator(); 
  500.   obj_link* p =  it ? v->adj_edges.move_to_succ() 
  501.                  : v->adj_edges.start_iteration(); 
  502.   return  e = edge(adj_link1(p));
  503.  }
  504.  
  505. inline bool graph::next_adj_node(node& w,node v)  const
  506. { edge e;
  507.   if (next_adj_edge(e,v))
  508.   { //w = (v==e->s) ? e->t : e->s;  // ugraph
  509.     w = e->t;
  510.     return true; 
  511.    }
  512.   else return false;
  513.  }
  514.    
  515. inline bool graph::current_adj_node(node& w,node v)  const
  516. { edge e;
  517.   if (current_adj_edge(e,v))
  518.   { //w = (v==e->s) ? e->t : e->s;  // ugraph
  519.     w = e->t;
  520.     return true; 
  521.    }
  522.   else return false;
  523. }
  524.    
  525.  
  526. inline node graph::first_node()   const { return node(node_link(V.first())); }
  527. inline node graph::last_node()    const { return node(node_link(V.last())); }
  528. inline node graph::choose_node()  const { return first_node(); }
  529.  
  530. inline edge graph::first_edge()   const { return edge(edge_link(E.first())); }
  531. inline edge graph::last_edge()    const { return edge(edge_link(E.last())); }
  532. inline edge graph::choose_edge()  const { return first_edge(); }
  533.  
  534. inline node graph::succ_node(node v)  const  
  535. { return node(node_link(V.succ(node_link(v)))); }
  536.  
  537. inline node graph::pred_node(node v)  const  
  538. { return node(node_link(E.pred(node_link(v)))); }
  539.  
  540. inline edge graph::succ_edge(edge e)  const  
  541. { return edge(edge_link(E.succ(edge_link(e)))); }
  542.  
  543. inline edge graph::pred_edge(edge e)  const  
  544. { return edge(edge_link(E.pred(edge_link(e)))); }
  545.  
  546. inline edge graph::adj_succ(edge e)  const
  547. { return edge(adj_link1(adj_link1(e)->succ_item())); }
  548.  
  549. inline edge graph::adj_pred(edge e)  const
  550. { return edge(adj_link1(adj_link1(e)->pred_item())); }
  551.  
  552. inline edge graph::cyclic_adj_succ(edge e) const 
  553. { return (e = adj_succ(e)) ? e : first_adj_edge(e->s); }
  554.  
  555. inline edge graph::cyclic_adj_pred(edge e) const 
  556. { return (e = adj_pred(e)) ? e : last_adj_edge(e->s); }
  557.  
  558. //------------------------------------------------------------------------------
  559. // Iteration   (macros)
  560. //------------------------------------------------------------------------------
  561.  
  562. #define forall_nodes(v,g) for (v=(g).first_node(); v; v=(g).succ_node(v) )
  563. #define forall_edges(e,g) for (e=(g).first_edge(); e; e=(g).succ_edge(e) )
  564.  
  565. #define Forall_nodes(v,g) for (v=(g).last_node(); v; v=(g).pred_node(v) )
  566. #define Forall_edges(e,g) for (e=(g).last_edge(); e; e=(g).pred_edge(e) )
  567.  
  568.  
  569. #define forall_adj_edges(e,v) for(e = First_Adj_Edge(v);e;e = Succ_Adj_Edge(e))
  570.  
  571. #define forall_out_edges(e,v) forall_adj_edges(e,v)
  572.  
  573. #define forall_in_edges(e,v) while(false)
  574.  
  575.  
  576. #define forall_adj_nodes(u,v)\
  577. for(start_adj_iteration(v); read_adj_node(u,v); move_to_adj_succ(v))
  578.  
  579.  
  580.  
  581. //------------------------------------------------------------------------------
  582. // GRAPH<vtype,etype> : parameterized directed graphs
  583. //------------------------------------------------------------------------------
  584.  
  585.  
  586. template<class vtype, class etype> 
  587.  
  588. class _CLASSTYPE GRAPH : public graph {
  589.  
  590. vtype X;
  591. etype Y;
  592.  
  593. void copy_node_entry(GenPtr& x) const  { x=Copy(ACCESS(vtype,x)); }
  594. void copy_edge_entry(GenPtr& x) const  { x=Copy(ACCESS(etype,x)); }
  595.  
  596. void clear_node_entry(GenPtr& x) const { Clear(ACCESS(vtype,x)); }
  597. void clear_edge_entry(GenPtr& x) const { Clear(ACCESS(etype,x)); }
  598.  
  599. void write_node_entry(ostream& o, GenPtr& x) const {Print(ACCESS(vtype,x),o);}
  600. void write_edge_entry(ostream& o, GenPtr& x) const {Print(ACCESS(etype,x),o);}
  601.  
  602. void read_node_entry(istream& i, GenPtr& x) { Read(X,i); x=Copy(X); }
  603. void read_edge_entry(istream& i, GenPtr& x) { Read(Y,i); x=Copy(Y); }
  604.  
  605. void init_node_entry(GenPtr& x) { Init(X); x = Copy(X); }
  606. void init_edge_entry(GenPtr& x) { Init(Y); x = Copy(Y); }
  607.  
  608. void print_node_entry(ostream& o, GenPtr& x)  const
  609.      { o << "("; Print(ACCESS(vtype,x),o); o << ")"; }
  610. void print_edge_entry(ostream& o, GenPtr& x)  const
  611.      { o << "("; Print(ACCESS(etype,x),o); o << ")"; }
  612.  
  613. char* node_type()  const { return TYPE_NAME(vtype); }
  614. char* edge_type()  const { return TYPE_NAME(etype); }
  615.  
  616. public:
  617.  
  618. int cmp_node_entry(node x, node y) const { return compare(inf(x),inf(y)); }
  619. int cmp_edge_entry(edge x, edge y) const { return compare(inf(x),inf(y)); }
  620.  
  621. vtype  inf(node v)    const   { return ACCESS(vtype,graph::inf(v)); }
  622. etype  inf(edge e)    const   { return ACCESS(etype,graph::inf(e)); }
  623.  
  624. vtype& operator[] (node v)    { return ACCESS(vtype,entry(v)); }
  625. etype& operator[] (edge e)    { return ACCESS(etype,entry(e)); }
  626. vtype  operator[] (node v) const   { return ACCESS(vtype,graph::inf(v)); }
  627. etype  operator[] (edge e) const   { return ACCESS(etype,graph::inf(e)); }
  628.  
  629. void   assign(node v,vtype x) { operator[](v) = x; }
  630. void   assign(edge e,etype x) { operator[](e) = x; }
  631.  
  632. node   new_node()               { return graph::new_node(); }
  633. node   new_node(vtype a)        { return graph::new_node(Copy(a)); }
  634.  
  635. edge   new_edge(node v, node w) { return graph::new_edge(v,w); }
  636. edge   new_edge(node v, node w, etype a)
  637.                                 { return graph::new_edge(v,w,Copy(a)); }
  638. edge   new_edge(edge e, node w) { return graph::new_edge(e,w); }
  639. edge   new_edge(edge e, node w, etype a)
  640.                                 { return graph::new_edge(e,w,Copy(a),0); }
  641. edge   new_edge(edge e, node w, etype a, int dir)
  642.                                 { return graph::new_edge(e,w,Copy(a),dir); }
  643.  
  644. void   clear()                  { clear_all_entries(); graph::clear(); }
  645.  
  646. GRAPH<vtype,etype>& operator=(const GRAPH<vtype,etype>& a)
  647. { clear_all_entries();graph::operator=(a);copy_all_entries();return *this; }
  648.  
  649. GRAPH()  {}
  650. GRAPH(const GRAPH<vtype,etype>& a) : graph(a) { a.copy_all_entries(); } 
  651.  
  652. /* subgraphs */
  653. GRAPH(GRAPH<vtype,etype>& a, const list<node>& b, const list<edge>& c) 
  654.                                                   : graph(a,b,c) {}
  655.  
  656. GRAPH(GRAPH<vtype,etype>& a, const list<edge>& c) : graph(a,c) {}
  657.  
  658. virtual ~GRAPH()   { if (parent==0) clear_all_entries(); }
  659.  
  660. };
  661.  
  662.  
  663.  
  664. //------------------------------------------------------------------------------
  665. // node_list
  666. //------------------------------------------------------------------------------
  667.  
  668. class node_list : public c_obj_list
  669. {
  670.   node iterator;
  671.  
  672. public:
  673.  
  674.   static void del_node(node v) { aux_link(v)->del_item(); }
  675.  
  676.   void append(node v) { c_obj_list::append(aux_link(v)); }
  677.   void push(node v)   { c_obj_list::push(aux_link(v)); }
  678.   void insert(node v, node w) 
  679.                       { c_obj_list::insert(aux_link(v),aux_link(w)); }
  680.   node pop()          { return node(aux_link(c_obj_list::pop())); }
  681.   void del(node v)    { c_obj_list::del(aux_link(v)); }
  682.  
  683.   bool member(node v)  const { return aux_link(v)->succ_link != nil; }
  684.   bool operator()(node v) const { return member(v); }
  685.  
  686.   node first()const { return node(aux_link(c_obj_list::first())); }
  687.   node last() const { return node(aux_link(c_obj_list::last()));  }
  688.   node head() const { return node(aux_link(c_obj_list::first())); }
  689.   node tail() const { return node(aux_link(c_obj_list::last()));  }
  690.  
  691.   node succ(node v) const
  692.   { return node(aux_link(c_obj_list::succ(aux_link(v)))); }
  693.  
  694.   node pred(node v) const
  695.   { return node(aux_link(c_obj_list::pred(aux_link(v)))); }
  696.  
  697.   node cyclic_succ(node v) const
  698.   { return node(aux_link(c_obj_list::cyclic_succ(aux_link(v)))); }
  699.  
  700.   node cyclic_pred(node v) const
  701.   { return node(aux_link(c_obj_list::cyclic_pred(aux_link(v)))); }
  702.  
  703.   void start_iteration() const { (*(node*)&iterator)=first(); }
  704.   void move_to_succ() const { (*(node*)&iterator) = succ(iterator);}
  705.  
  706.   bool read_iterator(node& x) const { x = iterator; return x ? true : false; }
  707.  
  708. };
  709.  
  710.  
  711.  
  712. //------------------------------------------------------------------------------
  713. // node_stack 
  714. //------------------------------------------------------------------------------
  715.  
  716. class node_stack {
  717.  
  718. node head;
  719.  
  720. public:
  721.  
  722. node_stack() { head = nil; }
  723.  
  724. void push(node v) { v->data[1] = head; head = v; }
  725. node pop()        { node v = head; head = node(v->data[1]); return v; }
  726. bool empty()      { return (head==nil) ? true : false; }  
  727. void clear()      { head = nil; }  
  728.  
  729. };
  730.  
  731.  
  732. //------------------------------------------------------------------------------
  733. // node_queue 
  734. //------------------------------------------------------------------------------
  735.  
  736. class node_queue {
  737.  
  738. node head;
  739. node tail;
  740.  
  741. public:
  742.  
  743. node_queue() { head = nil; }
  744.  
  745. void append(node v) 
  746. { v->data[1] = nil; 
  747.   if (head == nil) 
  748.      head = v;
  749.   else
  750.      tail->data[1] = v; 
  751.   tail = v; 
  752.  }
  753.  
  754. node pop()   { node v = head; head = node(v->data[1]); return v; }
  755. bool empty() { return (head==nil) ? true : false; }  
  756. void clear() { head = nil; }  
  757.  
  758. };
  759.  
  760.  
  761.  
  762. //------------------------------------------------------------------------------
  763. // node_data 
  764. //------------------------------------------------------------------------------
  765.  
  766.  
  767. template <class T> class node_data {
  768.  
  769. public:
  770.  
  771. T& operator[](node v) { return (T&)v->data[2]; }
  772.  
  773. node_data(const graph& G, T x) { init_node_data2(G,GenPtr(x)); }
  774.  
  775. };
  776.  
  777.  
  778. class int_node_data {
  779.  
  780. public:
  781.  
  782. int& operator[](node v) { return (int&)v->data[2]; }
  783. int  operator()(node v) { return (int)v->data[2]; }
  784.  
  785. int  get(node v) { return (int)v->data[2]; }
  786. void set(node v,int i) { v->data[2] = GenPtr(i); }
  787.  
  788. int_node_data(const graph& G, int x) { init_node_data2(G,GenPtr(x)); }
  789.  
  790. };
  791.  
  792.  
  793.  
  794.  
  795.  
  796. //------------------------------------------------------------------------------
  797. // edge_data 
  798. //------------------------------------------------------------------------------
  799.  
  800.  
  801. template <class T> class edge_data {
  802.  
  803. public:
  804.  
  805. T& operator[](edge e) { return (T&)e->data[1]; }
  806.  
  807. edge_data(const graph& G, T x) { init_edge_data(G,1,GenPtr(x)); }
  808.  
  809. };
  810.  
  811.  
  812.  
  813.  
  814. //------------------------------------------------------------------------------
  815. // node and edge arrays
  816. //------------------------------------------------------------------------------
  817.  
  818.  
  819. #if defined(LEDA_CHECKING_OFF)
  820. #define GRAPH_ARRAY_ACCESS(I,type)\
  821. type& operator[](I x)       { return ACCESS(type,arr[index(x)]); }\
  822. type  operator[](I x) const { return ACCESS(type,arr[index(x)]); }
  823. #else
  824. #define GRAPH_ARRAY_ACCESS(I,type)\
  825. type& operator[](I x)       { return ACCESS(type,entry(x));}\
  826. type  operator[](I x) const { return ACCESS(type,inf(x));}
  827. #endif
  828.  
  829. //------------------------------------------------------------------------------
  830. // node arrays
  831. //------------------------------------------------------------------------------
  832.  
  833.  
  834.  
  835. template<class type>
  836.  
  837. class _CLASSTYPE node_array : public graph_array<node> {
  838.  
  839. type X;
  840.  
  841. void copy_entry(GenPtr& x) const { x=Copy(ACCESS(type,x));}
  842. void clear_entry(GenPtr& x)const { Clear(ACCESS(type,x)); }
  843.  
  844. public:
  845.  
  846. int cmp_entry(node x,node y) const 
  847. { return compare(ACCESS(type,arr[index(x)]),ACCESS(type,arr[index(y)])); }
  848.  
  849. GRAPH_ARRAY_ACCESS(node,type)
  850.  
  851. type& elem(int i)              { return ACCESS(type,arr[i]);}
  852. type  elem(int i) const        { return ACCESS(type,arr[i]);}
  853.  
  854. void  init(const graph& G, int n, type i) { graph_array<node>::init(G,n,Convert(i)); }
  855. void  init(const graph& G, type i)        { init(G,G.max_i(node(0))+1,i); }
  856. void  init(const graph& G)                { Init(X); init(G,X); }
  857. void  init(const node_array& A)           { graph_array<node>::init(A); }
  858.  
  859.  
  860. node_array() {}
  861. node_array(const graph& G)                 { init(G);   }
  862. node_array(const graph& G, int n, type i)  { init(G,n,i); }
  863. node_array(const graph& G, type i)         { init(G,i); }
  864. node_array(const node_array& A)            { init(A);   }
  865.  
  866. node_array& operator=(const node_array& A) { init(A); return *this;}
  867.  
  868. ~node_array() { graph_array<node>::clear(); }
  869.  
  870. };
  871.  
  872.  
  873. //------------------------------------------------------------------------------
  874. // edge arrays
  875. //------------------------------------------------------------------------------
  876.  
  877.  
  878. template<class type>
  879.  
  880. class _CLASSTYPE edge_array : public graph_array<edge> {
  881.  
  882. type X;
  883.  
  884. void copy_entry(GenPtr& x) const { x=Copy(ACCESS(type,x));}
  885. void clear_entry(GenPtr& x)const { Clear(ACCESS(type,x)); }
  886.  
  887. public:
  888.  
  889. int cmp_entry(edge x,edge y) const 
  890. { return compare(ACCESS(type,arr[index(x)]),ACCESS(type,arr[index(y)])); }
  891.  
  892. GRAPH_ARRAY_ACCESS(edge,type)
  893.  
  894. type& elem(int i)              { return ACCESS(type,arr[i]);}
  895. type  elem(int i) const        { return ACCESS(type,arr[i]);}
  896.  
  897. void  init(const graph& G, int n, type i) { graph_array<edge>::init(G,n,Convert(i)); }
  898. void  init(const graph& G, type i)        { init(G,G.max_i(edge(0))+1,i); }
  899. void  init(const graph& G)                { Init(X); init(G,X); }
  900. void  init(const edge_array& A)           { graph_array<edge>::init(A); }
  901.  
  902. edge_array() {}
  903. edge_array(const graph& G)                 { init(G);   }
  904. edge_array(const graph& G, int n, type i)  { init(G,n,i); }
  905. edge_array(const graph& G, type i)         { init(G,i); }
  906. edge_array(const edge_array& A)            { init(A);   }
  907.  
  908. edge_array& operator=(const edge_array& A) { init(A); return *this;}
  909.  
  910. ~edge_array() { graph_array<edge>::clear(); }
  911.  
  912. };
  913.  
  914.  
  915.  
  916.  
  917.  
  918. //-----------------------------------------------------------------------------
  919. // graph generators
  920. //-----------------------------------------------------------------------------
  921.  
  922. extern void complete_graph(graph&,int);
  923. extern void random_graph(graph&,int,int);
  924. extern void test_graph(graph&);
  925.  
  926. extern void complete_bigraph(graph&,int,int,list<node>&,list<node>&);
  927. extern void random_bigraph(graph&,int,int,int,list<node>&,list<node>&);
  928. extern void test_bigraph(graph&,list<node>&,list<node>&);
  929.  
  930.  
  931. extern void random_planar_graph(graph&,node_array<double>& xcoord, 
  932.                                        node_array<double>& ycoord, int n);
  933.  
  934. extern void random_planar_graph(graph&,int);
  935.  
  936.  
  937. extern void grid_graph(graph&,node_array<double>& xcoord, 
  938.                               node_array<double>& ycoord, int n);
  939.  
  940. extern void grid_graph(graph&,int);
  941.  
  942.  
  943. extern void cmdline_graph(graph&,int,char**);
  944.  
  945.  
  946.  
  947. //-----------------------------------------------------------------------------
  948. // miscellaneous  (should be members or constructors)
  949. //-----------------------------------------------------------------------------
  950.  
  951. extern bool Is_Bidirected(const graph&, edge_array<edge>&);
  952.  
  953. extern bool Is_Simple(graph& G);
  954.  
  955. extern void Make_Simple(graph& G);
  956.  
  957.  
  958.  
  959. // for historical reasons:
  960.  
  961. inline bool compute_correspondence(const graph& G, edge_array<edge>& rev)
  962. { return Is_Bidirected(G,rev); }
  963.  
  964. inline void eliminate_parallel_edges(graph& G) 
  965. { Make_Simple(G); }
  966.  
  967.  
  968. #endif
  969.